package BinaryTrees;

import java.util.LinkedList;
import java.util.Queue;
import com.mj.printer.BinaryTreeInfo;

// 二叉树
@SuppressWarnings("unchecked")
public class BinaryTree <E> implements BinaryTreeInfo {
	protected int size;
	protected Node<E> root;

	// 节点
	protected static class Node <E> {
		E element;
		Node<E> left;
		Node<E> right;
		Node<E> parent;

		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}

		// 是否是叶子节点
		public boolean isLeaf() {
			return left == null && right == null;
		}

		// 是否拥有2个子节点
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
		
		// 是否是父节点的 左子节点
		public boolean isLeftChild() {
			return parent != null && this == parent.left;
		}
		
		// 是否是父节点的 右子节点
		public boolean isRightChild() {
			return parent != null && this == parent.right;
		}
	}

	// 访问者
	public static abstract class Visitor <E> {
		boolean stop;
		/*
		 * 如果返回ture就停止遍历
		 * */
		abstract boolean visit(E element);
	}

	// 返回节点数量
	public int size() {
		return size;
	}

	// 返回是否是空树
	public boolean isEmpty() {
		return size == 0;
	}

	// 清空二叉树
	public void clear() {
		root = null;
		size = 0;
	}
	
	protected Node<E> createNode (E element, Node<E> parent) {
		return new Node(element, parent);
	}

	// 寻找node的前驱节点(中序遍历时的前一个节点)
	@SuppressWarnings("unused")
	protected Node<E> predecessor(Node<E> node) {
		if (node == null) {
			return null;
		}

		// 如果node有左子节点,那么前驱节点一定在左子节点开始一直往右找
		Node<E> pNode = node.left;
		if (pNode != null) {
			while (pNode.right != null) {
				pNode = pNode.right;
			}
			return pNode;
		}

		// node没有左子节点,就从它的父/祖父节点中寻找
		while (node.parent != null && node == node.parent.left) {
			node = node.parent;
		}

		return node.parent;
	}

	// 寻找node的后继节点(中序遍历时的后一个节点)
	protected Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}

		// 如果node有右子节点,那么后继节点一定在右子节点开始一直往左找
		Node<E> pNode = node.right;
		if (pNode != null) {
			while (pNode.left != null) {
				pNode = pNode.left;
			}
			return pNode;
		}

		// node没有右子节点,就从它的父/祖父节点中寻找
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}

		return node.parent;
	}

	// 检查元素是否为空值
	protected void elementNoNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element can not be null");
		}
	}
	
	// 前序遍历
	public void preorderTraversal() {
		preorderTraversal(root);
	}

	private void preorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		System.out.println(node.element);
		preorderTraversal(node.left);
		preorderTraversal(node.right);
	}

	// 中序遍历
	public void inorderTraversal() {
		inorderTraversal(root);
	}

	private void inorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		inorderTraversal(node.left);
		System.out.println(node.element);
		inorderTraversal(node.right);
	}

	// 后序遍历
	public void postorderTraversal() {
		postorderTraversal(root);
	}

	private void postorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		postorderTraversal(node.left);
		postorderTraversal(node.right);
		System.out.println(node.element);
	}

	// 层序遍历
	public void levelOrderTraversal() {
		if (root == null) {
			return;
		}

		Queue<Node<E>> queue = new LinkedList<>();
		// 先将根节点入队
		queue.offer(root);

		// 然后出队的时候依次将左右节点入队
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			System.out.println(node.element);

			if (node.left != null) {
				queue.offer(node.left);
			}

			if (node.right != null) {
				queue.offer(node.right);
			}
		}
	}

	// 遍历停止由外界告知.
	public void preorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		preorder(root, visitor);
	}

	private void preorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
		preorder(node.left, visitor);
		preorder(node.right, visitor);
	}

	// 中序遍历
	public void inorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		inorder(root, visitor);
	}

	private void inorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}
		inorder(node.left, visitor);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
		inorder(node.right, visitor);
	}

	// 后序遍历
	public void postorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		postorder(root, visitor);
	}

	private void postorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}

		postorder(node.left, visitor);
		postorder(node.right, visitor);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
	}

	// 层序遍历
	public void levelOrder(Visitor<E> visitor) {
		if (root == null || visitor == null) {
			return;
		}

		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();

			if (visitor.visit(node.element)) {
				return;
			} 

			if (node.left != null) {
				queue.offer(node.left);
			}

			if (node.right != null) {
				queue.offer(node.right);
			}	
		}
	}
	
	
	@SuppressWarnings("unused")
	private int height2(Node<E> node) {
		if (node == null) return 0;
		return 1 + Math.max(height(node.left), height(node.right));
	}

	// 获取二叉树的高度
	public int height() {
		return height(root);
	}

	private int height(Node<E> node) {
		if (node == null) {
			return 0;
		}
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(node);
		// 树的高度
		int height = 0;
		// 一层节点数量
		int levelSize = 1;
		while (!queue.isEmpty()) {
			Node<E> node2 = queue.poll();
			levelSize--;

			if (node2.left != null) {
				queue.offer(node2.left);
			}

			if (node2.right != null) {
				queue.offer(node2.right);
			}

			if (levelSize == 0) {
				levelSize = queue.size();
				height ++;
			}
		}

		return height;
	}

	public String toString() {
		StringBuilder sBuilder = new StringBuilder();
		toString(root, sBuilder, "");
		return sBuilder.toString();
	}

	private void toString(Node<E> node, StringBuilder sBuilder, String prefix) {
		if (node == null) {
			return ;
		}
		toString(node.left, sBuilder, "L---");
		sBuilder.append(prefix).append(node.element).append("\n");
		toString(node.right, sBuilder, "R---");
	}

	// 是否是完全二叉树
	public boolean isComplete() {
		if (root == null) {
			return false;
		}
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);
		Boolean isLeaf = false;
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (isLeaf && node.isLeaf()) {
				return false;
			}

			if (node.left != null) {
				queue.offer(node.left);
			} else if (node.right != null) {
				return false;
			}

			if (node.right != null) {
				queue.offer(node.right);
			} else {
				isLeaf = true;
			}
		}
		return true;
	}


	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return root;
	}

	
	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
		return node;
	}
}
